Clos circuit switch has been proposed by Clos in 1953 at Bell Labs (C. Clos, “A study of non-blocking switching networks,” Bell Systems Technology Journal 32:406-424 (1953)). FIG. 1 shows the connections between switching elements (SE) in a symmetric Clos three-stage switch. This interconnection rule is: the xth SE in some switching stage is connected to the xth input of each SE in the next stage (C. Clos, 32:406-424 (1953); J. Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Press 1990; F. K. Hwang, The mathematical theory of nonblocking switching networks, World Scientific, 1998). Here, all connections have the same bandwidths. It has been shown that a circuit can be established through the Clos switching fabric without rearranging existing circuits as long as the number of SEs in the second stage is at least twice the number of inputs of an SE in the first stage, i.e. l≧2 n. It has also been shown that a circuit can be established through the Clos switching fabric as long as the number of SEs in the second stage is no less than the number of inputs of an SE in the first stage, i.e. l≧n. In the latter case, the number of required SEs and their total capacity are smaller due to the fact that the existing circuits can be rearranged. While the complexity of the switching fabric hardware is reduced, the complexity of the algorithm for a circuit setup is increased. In both cases, non-blocking property of the Clos architecture has been proven assuming the specific algorithms for circuit setup (F. K. Hwang, World Scientific, 1998). Various implications of Clos findings have been examined in W. Kabacinski et al. “50th anniversary of Clos networks,” IEEE Communication Magazine, 41(10): 26-64 (October 2003).
The Clos switching fabric can be used for increasing capacity of packet switches as well. The interconnection of SEs would be the same as in the circuit switch case. However, these SEs should be reconfigured in each cell time slot based on the outputs of outstanding cells. Here, packets are split into cells of a fixed duration which is typically 50 ns (64 bytes at 10 Gb/s). Algorithms for circuit setup in Clos circuit switches cannot be readily applied in Clos packet switches. First, all SEs should be synchronized on a cell-by-cell basis. Then, an implementation of the algorithm that rearranges connections on a cell-by-cell basis in SEs of a rearrangeable non-blocking Clos switch would be prohibitively complex (J. Hui, Kluwer Academic Press 1990). So, the Clos fabric with the larger hardware, l=2n, is needed for a non-blocking packet switch. A scheduling algorithm that would provide non-blocking in a Clos packet switch would require higher processing complexity than its counterpart designed for a cross-bar switch (A. Smiljanić, “Flexible bandwidth allocation in terabit packet switches,” Proceedings of IEEE Conference on High Performance Switching and Routing, June 2000, pp. 233-241; A. Smiljanić, “Flexible Bandwidth Allocation in High-Capacity Packet Switches,” IEEE/ACM Transactions on Networking, April 2002, pp. 287-293). Few heuristics have been proposed to configure SEs in Clos packet switches without assessment of their blocking nature (McDermott et al., “Large-scale IP router using a high-speed optical switch element,” OSA Journal on Optical Networking, www.osa-jon.org, July 2003, pp. 228-241; Oki et al., “Concurrent round-robin-based dispatching schemes for Clos-network switches,” IEEE/ACM Transactions on Networking, 10(6):830-844 (December 2002)).
On the other side, it has been recognized that a Clos packet switch in which the traffic load is balanced across the SEs provides non-blocking, i.e. with sufficiently large buffers it passes all the traffic if the outputs are not over-loaded. Such an architecture has been described in Chaney et al., “Design of a gigabit ATM switch,” Proceedings of INFOCOM 1997, 1:2-11 (1997) and J. S. Turner, “An optimal nonblocking multicast virtual circuit switch,” Proceeding of INFOCOM 1994, 1:298-305 (1994). Turner showed that the architecture is non-blocking if the traffic of each multicast session is balanced over the SEs in a Benes packet switch. Here the multicast session carries the information between end users in the network.
However, the delay that packets experience through the Clos switch has not been assessed. Delay guarantees are important for various applications, for example, interactive voice and video, web browsing, streaming etc. In previous work, flows of data belonging to individual multicast sessions were balanced over switching elements (SEs) in the middle stage. The delay for such load balancing mechanism is too long. In order to guarantee acceptable delays for sensitive applications, the utilization of the mechanisms that balances loads of individual sessions decreases unacceptably with switch size (A. Smiljanić, “Performance load balancing algorithm in Clos packet switches,” Proceedings of IEEE Workshop on High Performance Switching and Routing, 2004; A. Smiljanić, “Load balancing algorithm in Clos packet switches,” Proceedings of IEEE International Conference on Communications, 2004). Accordingly, a challenge in the field is providing a minimum required delay guarantee without unacceptably decreasing fabric utilization.